# 暴力枚举
class Solution(object):
    def numSquares(self, n):
        """
        :type n: int
        :rtype: int
        """
        DP = [0] * n
        for i in range(1, n + 1):
            if (int(i ** 0.5)) ** 2 == i:
                DP[i - 1] = 1
            else:
                min_value = i
                for j in range(1, i // 2 + 1):
                    min_value = min(DP[j - 1] + DP[i - j - 1], min_value)
                DP[i - 1] = min_value
        return DP[-1]

# 优化枚举
class Solution(object):
    def numSquares(self, n):
        """
        :type n: int
        :rtype: int
        """
        DP = [i + 1 for i in range(n)]
        for i in range(1, n + 1):
            j = int(i ** 0.5)
            if j ** 2 == i:
                DP[i - 1] = 1
            else:
                for k in range(1, j + 1):
                    DP[i - 1] = min(1 + DP[i - k ** 2 - 1], DP[i - 1])
        return DP[-1]

data = Solution()
n = 6110
print(data.numSquares(n))
